package com.lry.basic.algorithm.stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

//https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
class LargestRectangleArea {

    public static void main(String[] args) {
        System.out.println(largestRectangleArea(new int[]{2,1,5,6,2,3}));
        System.out.println(largestRectangleArea2(new int[]{2,1,5,6,2,3}));
    }

    public static int largestRectangleArea2(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];

        for (int i = 0; i < heights.length; ++i) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[i] = (stack.isEmpty() ? -1 : stack.peek());
            stack.push(i);
        }


        stack.clear();
        for (int i = heights.length - 1; i >= 0; --i) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            right[i] = (stack.isEmpty() ? heights.length : stack.peek());
            stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < heights.length; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }

        return ans;
    }

    public static int largestRectangleArea(int[] heights) {
        int max = 0;

        for(int i=0;i<heights.length;i++){
            int left = i;
            while(left>=0){
                if(heights[left]>=heights[i]){
                    left--;
                }else{
                    break;
                }
            }
            int right = i;
            while(right<heights.length){
                if(heights[right]>=heights[i]){
                    right++;
                }else{
                    break;
                }
            }
            max = Math.max(max,(right-left-1)*heights[i]);
        }

        return max;
    }
}